Routers include network interfaces, to which links from other routers may be connected. The network interfaces are typically handled by device drivers (software) executed by processors. The network interfaces and/or the device drivers enqueue packets received by the network interfaces onto queues for subsequent processing. For example, the subsequent processing may involve simply enqueuing the packet for transmission by an outgoing network interface, or the processing may be more complex, such as resolving the packet's destination address.
Each queue may be handled by a different processor. Distributing the incoming packets across a plurality of queues, and therefore a plurality of processors, enables the incoming packets to be processed more quickly than if a single processor handled all the packets received by the network interfaces. Such a scheme is used in the well-known receive side scaling (RSS) network driver technology.
However, with more than one network interface, the queue-to-processor assignment task becomes complex. Assigning processors to queues of multiple network interfaces poses problems. Typically, fewer processors are available than queues. Therefore, most or all of the processors handle multiple queues. However, assigning a given processor to handle two or more queues associated with one network interface provides no advantage and can decrease performance. Furthermore, unequally distributing the processors to the queues can cause delays of packets, or dropping of packets, received by network interfaces that are underserved by the processors. On the other hand, assigning excessive numbers of processors to some of the queues, at the expense of other queues, wastes valuable processor resources.
No known prior art assignment scheme, such as round-robin assignment of processors in numerical order to queues, is likely to evenly distribute the workload across the processors. Consequently, some of the processors can be overloaded, while other processors remain idle or only lightly loaded.